IP routing protocols use SPF methods to compute and select the shortest path to a network destination. IP routing protocols that use SPF methods have conventionally implemented path cost calculations assuming that each network device is a single node. In these networks, all potential paths between the source and destination IP devices are identified through network topology information provided by network devices through link state advertisement (LSA) or similar status messages. Costs are assigned to each network segment by a network administrator to reflect relative geographic distance, equipment cost, or other network attributes as deemed appropriate by the administrator. Conventionally, assigned cost values are constrained to be zero or positive, and cost metrics have relative meaning only.
One SPF algorithm conventionally calculates an aggregate sum of the network segment costs for each of a set of predefined paths from a source IP device to a destination IP device, and the path with the lowest cost is selected by the source IP device for data transfers. Multiple paths having the same aggregate cost may be utilized by the source IP device in a load-sharing configuration where the total data traffic is distributed across all paths. The path lists generated by conventional SPF calculations do not permit an IP device to autonomously identify alternate paths to a destination IP device for the purposes of either distributing data traffic for load-balancing or for redirecting traffic under a segment or IP device failure in the data network. If an IP device experiences traffic load demands beyond the capacity of the preferred path identified by the SPF calculation, the excess traffic is discarded. Likewise, if a network node or segment in the lowest cost path fails, the IP device cannot autonomously redirect its data traffic. Until new path definitions are provided by other network nodes through link state advertisement messages, data traffic flows are interrupted and requests for establishment of new VoIP call connections are rejected due to blockage.
One published protocol commonly used in public data networks, called Open Shortest Path First (OSPF), utilizes the basic SPF algorithm and methods. OSPF is defined to support general purpose unidirectional data traffic, such as file or webpage retrieval from a remote server. However, the OSPF definitions do not include methods to pre-assign alternate paths, nor do they include methods for data traffic recovery under node or segment failures along the preferred path. Similarly, the OSPF definitions do not include methods to constrain data traffic assignment among a group of equal low-cost paths in a load-balancing application.
OSPF has been extended to support modified segment cost definitions to support real-time traffic. This modified algorithm, called Traffic Engineering OSPF (TE-OSPF), continues to utilize the fundamental SPF calculation method. Applications that require interactive or low-latency data transfers between two IP devices, such as VoIP or interactive video services, typically have predefined levels of service quality to meet. These service quality levels are conventionally defined in terms of data throughput rates, maximum path delay, and percent availability, and these levels are commonly defined such that the service cannot tolerate data flow interruptions. However, the TE-OSPF definitions, like the OSPF definitions, do not support definitions of pre-assigned alternate paths for rapid network failure recovery or provide mechanisms to constrain load balancing among multiple lowest-cost paths. Systems supporting low-latency or interactive data traffic are consequently limited in their ability to implement the functions often required to support the defined service quality levels.
Accordingly, in light of these difficulties associated with obtaining a ranked list of paths to a destination IP device across a data network based on path costs, there exists a need for improved methods, systems, and computer program products for multi-path SPF computations and distance-based interface selection for VoIP traffic.